home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-03
/
iqb9109.zip
/
QSORT.BAS
< prev
next >
Wrap
BASIC Source File
|
1991-09-09
|
3KB
|
90 lines
' QSort.Bas
' QuickSort subprogram and RandInt% function extracted from the
' Microsoft-supplied program SORTDEMO.BAS.
' Portions Copyright by Microsoft Corporation.
'
' $INCLUDE: 'QSORT.BI'
' ============================== QuickSort ===================================
' QuickSort works by picking a random "pivot" element in SortArray, then
' moving every element that is bigger to one side of the pivot, and every
' element that is smaller to the other side. QuickSort is then called
' recursively with the two subdivisions created by the pivot. Once the
' number of elements in a subdivision reaches two, the recursive calls end
' and the array is sorted.
' ============================================================================
'
SUB QuickSort (Low AS INTEGER, High AS INTEGER)
DIM RandIndex AS INTEGER
DIM I AS INTEGER, J AS INTEGER
DIM Partition AS SortType
IF Low < High THEN
' Only two elements in this subdivision; swap them if they are out of
' order, then end recursive calls:
IF High - Low = 1 THEN
' Here's where the recursion terminates. If the two elements
' of this subdivision are out of order, swap them.
IF SortArray(Low).SortKey > SortArray(High).SortKey THEN
SWAP SortArray(Low), SortArray(High)
END IF
ELSE
' Pick a pivot element at random, then move it to the end:
RandIndex = RandInt%(Low, High)
SWAP SortArray(High), SortArray(RandIndex)
Partition.SortKey = SortArray(High).SortKey
DO
' Move in from both sides towards the pivot element:
I = Low: J = High
DO WHILE (I < J) AND (SortArray(I).SortKey <= Partition.SortKey)
I = I + 1
LOOP
DO WHILE (J > I) AND (SortArray(J).SortKey >= Partition.SortKey)
J = J - 1
LOOP
' If we haven't reached the pivot element, it means that two
' elements on either side are out of order, so swap them:
IF I < J THEN
SWAP SortArray(I), SortArray(J)
END IF
LOOP WHILE I < J
' Move the pivot element back to its proper place in the array:
SWAP SortArray(I), SortArray(High)
' Recursively call the QuickSort procedure (pass the smaller
' subdivision first to use less stack space):
IF (I - Low) < (High - I) THEN
QuickSort Low, I - 1
QuickSort I + 1, High
ELSE
QuickSort I + 1, High
QuickSort Low, I - 1
END IF
END IF
END IF
END SUB
' =============================== RandInt% ===================================
' Returns a random integer greater than or equal to the Lower parameter
' and less than or equal to the Upper parameter.
' ============================================================================
'
FUNCTION RandInt% (Lower AS INTEGER, Upper AS INTEGER) STATIC
RandInt% = INT(RND * (Upper - Lower + 1)) + Lower
END FUNCTION